const mergeSort = (arr) => {
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right));
}

const merge = (arr1,arr2) => {
    let len1 = arr1.length, len2 = arr2.length;
    let len = len1 + len2;
    let array = [];
    for (let index=0,i = 0, j=0; index < len; index++) {
        if(i >= len1){
            array[index] = (arr2[j++])
        }else if(j >= len2){
            array[index] = (arr1[i++])
        }else if(arr1[i] < arr2[j]){
            array[index] = (arr1[i++]);
        }else{
            array[index] = (arr2[j++]);
        }
    }
    return array;
}

let nums = [1,9,8,3,5,6,4];
console.log((mergeSort(nums)));

